Field of the Invention
The present invention generally relates to scheduling a tree-like multi-cluster tool. In particular, the present invention relates to a method for scheduling this multi-cluster tool to thereby generate an optimal one-wafer cyclic schedule.
List of References
There follows a list of references that are occasionally cited in the specification. Each of the disclosures of these references is incorporated by reference herein in its entirety.                W. K. Chan, J. G. Yi, and S. W. Ding, “Optimal Scheduling of Multicluster Tools with Constant Robot Moving Times, Part I: Two-Cluster Analysis,” IEEE Transactions on Automation Science and Engineering, vol. 8, no. 1, pp. 5-16, 2011a.        W. K. Chan, J. G. Yi, S. W. Ding, and D. Z. Song, “Optimal Scheduling of Multicluster Tools with Constant Robot Moving Times, Part II: Tree-Like Topology Configurations,” IEEE Transactions on Automation Science and Engineering, vol. 8, no. 1, pp. 17-28, 2011b.        T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms: MIT press, 2001.        M. Dawande, C. Sriskandarajah, and S. P. Sethi, “On Throughput Maximization in Constant Travel-time Robotic Cells,” Manufacture Service Operation Manage, vol. 4, no. 4, pp. 296-312, 2002.        S. W. Ding, J. G. Yi, and M. T. Zhang, “Multicluster Tools Scheduling: an Integrated Event Graph and Network Model Approach,” IEEE Transactions on Semiconductor Manufacturing, vol. 19, no. 3, pp. 339-351, 2006.        I. Drobouchevitch, S. P. Sethi, and C. Sriskandarajah, “Scheduling Dual Gripper Robotic Cells: One-unit Cycles,” European Journal of Operational Research, vol. 171, no. 2, pp. 598-631, 2006.        H. Geismar, C. Sriskandarajah, and N. Ramanan, “Increasing Throughput for Robotic Cells With Parallel Machines and Multiple Robots,” IEEE Transactions on Automation Science and Engineering, vol. 1, no. 1, pp. 84-89, 2004.        J. -H. Kim, T. -E. Lee, H. -Y. Lee, and D. -B. Park, “Scheduling analysis of timed-constrained dual-armed cluster tools,” IEEE Transactions on Semiconductor Manufacturing, vol. 16, no. 3, pp. 521-534, 2003.        J. -H. Lee, T. -E. Lee, “Concurrent processing of multiple wafer types in a single-armed cluster tool,” IEEE Conference on Automation Science and Engineering, pp. 102-107, 2011.        T. -E. Lee, H. -Y. Lee, and Y. -H. Shin, “Workload balancing and scheduling of a single-armed cluster tool,” in Proceedings of the 5th APIEMS Conference, Gold Coast, Australia, pp. 1-15, 2004.        T. -E. Lee and S. -H. Park, “An extended event graph with negative places and tokens for timed window constraints,” IEEE Transactions on Automation Science and Engineering, vol. 2, no. 4, pp. 319-332, 2005.        M. -J. Lopez and S. -C. Wood, “Systems of multiple cluster tools—configuration, reliability, and performance,” IEEE Transactions on Semiconductor Manufacturing, vol. 16, no. 2, pp. 170-178, 2003.        T. Murata, “Petri nets: Properties, analysis and applications,” Proceedings of IEEE, vol. 77, no. 4, pp. 541-580, April 1989.        M. X. Liu and B. H. Zhou, “Modelling and scheduling analysis of multi-cluster tools with residency constraints based on time constraint sets”. International Journal of Production Research, vol. 51, no. 16, pp. 4835-4852, 2013.        T. L. Perkinson, P. K. MacLarty, R. S. Gyurcsik, and R. K. Cavin III, “Single-wafer cluster tool performance: An analysis of throughput,” IEEE Transactions on Semiconductor Manufacturing, vol. 7, no. 3, pp. 369-373, 1994.        T. L. Perkinson, R. S. Gyurcsik, and P. K. MacLarty, “Single-wafer cluster tool performance: An analysis of the effects of redundant chambers and revisitations sequences on throughput,” IEEE Transactions on Semiconductor Manufacturing, vol. 9, no. 3, pp. 384-400, 1996.        Y. Qiao, N. Q. Wu, and M. C. Zhou, “Petri Net Modeling and Wafer Sojourn Time Analysis of Single-Arm Cluster Tools With Residency Time Constraints and Activity Time Variation,” IEEE Transactions on Semiconductor Manufacturing, vol. 25, no. 3, pp. 432-446, 2012a.        Y. Qiao, N. Q. Wu, and M. C. Zhou, “Real-Time Scheduling of Single-Arm Cluster Tools Subject to Residency Time Constraints and Bounded Activity Time Variation,” IEEE Transactions on Automation Science and Engineering, vol. 9, no. 3, pp. 564-577, 2012b.        Y. Qiao, N. Q. Wu, and M. C. Zhou, “A Petri netbased Novel Scheduling Approach and Its Cycle Time Analysis for Dual-Arm Cluster Tools with Wafer Revisiting,” IEEE Transactions on Semiconductor Manufacturing, vol. 26, no. 1, pp. 100-110, 2013.        S. Rostami, B. Hamidzadeh, and D. Camporese, “An optimal periodic scheduler for dual-arm robots in cluster tools with residency constraints,” IEEE Transactions on Robotics and Automation, vol. 17, no. 5, pp. 609-618, 2001.        S. Venkatesh, R. Davenport, P. Foxhoven, and J. Nulman, “A steady state throughput analysis of cluster tools: Dual-blade versus single-blade robots,” IEEE Transactions on Semiconductor Manufacturing, vol. 10, no. 4, pp. 418-424, 1997.        N. Q. Wu, “Necessary and Sufficient Conditions for Deadlock-free Operation in Flexible Manufacturing Systems Using a Colored Petri Net Model,” IEEE Transaction on Systems, Man, and Cybernetics, Part C, vol. 29, no. 2, pp. 192-204, 1999.        N. Q. Wu, C. B. Chu, F. Chu, and M. C. Zhou, “A Petri net method for schedulability and scheduling problems in single-arm cluster tools with wafer residency time constraints,” IEEE Transactions on Semiconductor Manufacturing, vol. 21, no. 2, pp. 224-237, 2008.        N. Q. Wu, F. Chu, C. B. Chu, and M. C. Zhou, “Petri net modeling and cycle time analysis of dual-arm cluster tools with wafer revisiting,” IEEE Transactions on Systems, Man, & Cybernetics: Systems, vol. 43, no. 1, pp. 196-207, 2013a.        N. Q. Wu, F. Chu, C. Chu, and M. Zhou, “Petri Net-Based Scheduling of Single-Arm Cluster Tools With Reentrant Atomic Layer Deposition Processes,” IEEE Transactions on Automation Science and Engineering, vol. 8, no. 1, pp. 42-55, 2011.        N. Q. Wu, F. Chu, C. B. Chu, and M. C. Zhou, “Petri net modeling and cycle time analysis of dual-arm cluster tools with wafer revisiting,” IEEE Transactions on Systems, Man, & Cybernetics: Systems, vol. 43, no. 1, pp. 196-207, 2013b.        N. Q. Wu and M. C. Zhou, “Avoiding deadlock and reducing starvation and blocking in automated manufacturing systems based on a Petri net model,” IEEE Transactions on Robotics and Automation, vol. 17, no. 5, 658-669, 2001.        N. Q. Wu and M. C. Zhou, “Modeling and deadlock control of automated guided vehicle systems,” IEEE/ASME Transactions on Mechatronics, vol. 9, no. 1, pp. 50-57, 2004.        N. Q. Wu and M. C. Zhou, System modeling and control with resource-oriented Petri nets, CRC Press, Taylor & Francis Group, New York, October 2009.        N. Q. Wu and M. Zhou, “Analysis of wafer sojourn time in dual-arm cluster tools with residency time constraint and activity time variation,” IEEE Transactions on Semiconductor Manufacturing, vol. 23, no. 1, pp. 53-64, 2010a.        N. Q. Wu and M. C. Zhou, “A closed-form solution for schedulability and optimal scheduling of dual-arm cluster tools based on steady schedule analysis,” IEEE Transactions on Automation Science and Engineering, vol. 7, no. 2, pp. 303-315, 2010b.        N. Q. Wu and M. C. Zhou, “Modeling, analysis and control of dual-arm cluster tools with residency time constraint and activity time variation based on Petri nets,” IEEE Transactions on Automation Science and Engineering, vol. 9, no. 2, 446-454, 2012a.        N. Q. Wu and M. C. Zhou, “Schedulability analysis and optimal scheduling of dual-arm cluster tools with residency time constraint and activity time variation,” IEEE Transactions on Automation Science and Engineering, vol. 9, no. 1, pp. 203-209, 2012b.        N. Q. Wu, M. C. Zhou, F. Chu, and C. B. Chu, “A Petri-net-based scheduling strategy for dual-arm cluster tools with wafer revisiting,” IEEE Transactions on Systems, Man, & Cybernetics: Systems, vol. 43, no. 5, pp. 1182-1194, September 2013b.        N. Q. Wu, M. C. Zhou, and Z. W. Li, Resource-oriented Petri net for deadlock avoidance in flexible assembly systems, IEEE Transactions on System, Man, & Cybernetics, Part A, vol. 38, no. 1, 56-69, 2008b.        F. J. Yang, N. Q. Wu, Y. Qiao, and M. C. Zhou, Optimal one-wafer cyclic scheduling of single-arm multi-cluster tools with two-space buffering modules, IEEE Transactions on Systems, Man, & Cybernetics: Systems, vol. 44, no. 12, 1584-1597, 2014.        J. Yi, S. Ding, and D. Song, “Steady-state throughput and scheduling analysis of multi-cluster tools for semiconductor manufacturing: A decomposition approach,” in Proceedings of 2005 IEEE International Conference on Robotics and Automation, pp. 292-298, 2005.        J. G. Yi, S. W. Ding, D. Z. Song, and M. T. Zhang, “Steady-State Throughput and Scheduling Analysis of Multi-Cluster Tools for Semiconductor Manufacturing: A Decomposition Approach,” IEEE Transactions on Automation Science and Engineering, vol. 5, no. 2, pp. 321-336, 2008.        M. C. Zhou and M. D. Jeng, “Modeling, Analysis, Simulation, Scheduling, and Control of Semiconductor Manufacturing Systems: A Petri Net Approach,” IEEE Transactions on Semiconductor Manufacturing, vol. 11, no. 3, pp. 333-357, 1998.        W. M. Zuberek, “Timed Petri nets in modeling and analysis of cluster tools,” IEEE Transactions on Robotics Automation, vol. 17, no. 5, pp. 562-575, October 2001.        Q. H. Zhu, N. Q. Wu, Y. Qiao, and M. C. Zhou, “Scheduling of Single-Arm Multi-Cluster Tools to Achieve the Minimum Cycle Time,” in Proceedings of 2013 IEEE International Conference on Robotics and Automation, Karlsruhe, Germany, pp. 3555-3560, May 2013a.        Q. H. Zhu, N. Q. Wu, Y. Qiao, and M. C. Zhou, “Petri Net-Based Optimal One-Wafer Scheduling of Single-Arm Multi-Cluster Tools in Semiconductor Manufacturing,” IEEE Transactions on Semiconductor Manufacturing, vol. 26, no. 4, pp. 578-591, 2013b.        Q. H. Zhu, N. Q. Wu, Y. Qiao, and M. C. Zhou, “Modeling and Schedulability Analysis of Single-Arm Multi-Cluster Tools with Residency Time Constraints via Petri Nets” in Proc. IEEE Int. Conf. Auto. Sci. Eng., Taipei, Taiwan, pp. 81-86, 2014.        Q. H. Zhu, N. Q. Wu, Y. Qiao, and M. C. Zhou, “Scheduling of Single-Arm Multi-cluster Tools With Wafer Residency Time Constraints in Semiconductor Manufacturing” IEEE Transactions on Semiconductor Manufacturing, vol. 28, no. 1, 2015.        
There follows a list of patent(s) and patent application(s) that are occasionally cited in the specification.                D. Jevtic, “Method and Apparatus for Managing Scheduling a Multiple Cluster Tool,” European Patent Application Publication No. 1,132,792 A2, Sep. 12, 2001.        D. Jevtic and S. Venkatesh, “Method and Apparatus for Scheduling Wafer Processing within a Multiple Chamber Semiconductor Wafer Processing Tool Having a Multiple Blade Robot,” U.S. Pat. No. 6,224,638 B1, May 1, 2001.        
Description of Related Art
With single wafer processing technology, cluster tools are increasingly used in the semiconductor industry. Generally, a single-cluster tool is composed of four to six process modules (PM), one wafer-delivering robot (R), and two loadlocks (LL) for cassette loading/unloading. The robot can be single or dual-arm one resulting in single or dual-arm cluster tools. Several single-cluster tools are connected together by shared buffer modules (BMs) to form a more integrated manufacturing system called a multi-cluster tool. It has higher performance and becomes more and more popular in the semiconductor industry. However, it is very challenging to effectively operate such a system.
Extensive studies have been done on modeling, performance evaluation, and scheduling for single-cluster tools [Kim et al., 2003; Lee et al., 2004; Lee and Park, 2005; Lopez and Wood, 2003; Wu et al., 2008a; Wu and Zhou, 2010b; Qiao et al., 2012a and 2012b; and Wu et al., 2013a and 2013b]. It is found that a cluster tool may operate in process-bound or transport-bound region. For a single-cluster tool, if one of its process steps is the bottleneck of the tool in the sense of workload, it is process-bound. In this case, the cycle time of the system is determined by the wafer processing time. Otherwise, if the robot is the bottleneck, it is transport-bound and the cycle time is determined by the robot task time. In practice, the robot task time is much shorter than the wafer processing time [Kim et al., 2003; and Lopez and Wood, 2003] such that, for a single-arm cluster tool, a backward strategy is shown to be optimal [Lee et al., 2004; Dawande 2002; and Lopez and Wood, 2003]. Some wafer fabrication processes require that a processed wafer should leave a PM within a given time interval, which is called wafer residency time constraints [Kim et al., 2003; Lee and Park, 2005]. Without immediate buffer between the PMs in a tool, this greatly complicates the problem of scheduling single-cluster tools. This problem is studied by using Petri nets and mathematical programming models for dual-arm cluster tools to find an optimal periodic schedule in [Kim et al., 2003; Lee and Park, 2005]. It is further studied for both single and dual-arm cluster tools in [Wu et al., 2008; Wu and Zhou, 2010b; and Qiao et al., 2012a and 2012b] by developing generic Petri net (PN) models. With these models, robot waiting is explicitly modeled as an event to parameterize a schedule by robot waiting time. Then, to find a schedule is to determine the robot waiting time. With these models, schedulability conditions are presented and closed-form scheduling algorithms are given to find an optimal periodic schedule if schedulable.
In recent years, attention has been paid to the problem of scheduling multi-cluster tools. A multi-cluster tool composed of K single-cluster tools is called a K-cluster tool. A heuristic method is proposed in [Jevtic, 2001] for it by dynamically assigning priorities to PMs. However, the performance of such a schedule is difficult to evaluate. Geismar et al. examine a serial 3-cluster tool composed of single-arm tools and parallel processing modules. By simulation, they find that, for 87% of instances, the backward strategy achieves the lower-bound of cycle time. In [Ding et al., 2006], an event graph model is used to describe the dynamic behavior of the system and a simulation-based search method is proposed to find a periodic schedule.
To reduce the computational complexity, without considering the robot moving time, a decomposition method is proposed in [Yi et al., 2005 and 2008]. By this method, the fundamental period (FP) for each tool is calculated as done for scheduling single-cluster tools. Then, by analyzing time delays resulting from accessing the shared buffers, the global fundamental period, or the cycle time for the system is determined. In this way, a schedule is found.
With robot moving time considered, a polynomial algorithm is presented to find a multi-wafer schedule for a serial multi-cluster tool in [Chan et al., 2011a]. A K-cluster tool is said to be process-dominant if its bottleneck tool is process-bound. It is known that there is always an optimal one-wafer schedule for a process-dominant serial multi-cluster tool [Zhu et al., 2013a, 2012; and Zhu et al., 2013b]. In studying the effect of buffer spaces in BMs on productivity, Yang et al. [2014] show that, for a process-dominant serial multi-cluster tool with two-space BMs, there is a one-wafer cyclic schedule such that the lower bound of cycle time is reached. For a single-arm multi-cluster tool with two-space BMs and wafer residency time constraints, Liu and Zhou [2013] propose a non-linear programming model and a heuristic algorithm to solve it. For a single-arm multi-cluster tool with single-space BMs and wafer residency time constraints, Zhu et al. [2014 and 2015] present sufficient and necessary schedulability conditions and an efficient algorithm to find a one-wafer optimal cyclic schedule if schedulable.
Chan et al. [2011b] study the problem of scheduling a tree-like multi-cluster tool, which is the only report on tree-like multi-cluster tool scheduling to our best knowledge. The obtained schedule is a multi-wafer cyclic one. It derives conditions under which a tree-like multi-cluster tool can be scheduled by a decomposition method. Further, if decomposable, conditions under which a backward scheduling strategy is optimal are presented.
Since a one-wafer cyclic schedule is easy to implement and understand by a practitioner, it gives rise to a question if there exists a one-wafer cyclic schedule for a tree-like multi-cluster tool and how such a schedule can be found if it exists. There is a need in the art to derive the conditions for which this schedule exists and to develop a method for scheduling a tree-like multi-cluster tool with a one-wafer cyclic schedule.